# 作者：一只牛吗
# 2025 年03月 05日 02时 43分 40秒
# 1278599690@qq.com
class TreeNode:
    def __init__(self, val=-1, left_child=None, right_child=None):
        self.val = val
        self.left_child = left_child
        self.right_child = right_child


class BiTree:
    def __init__(self):
        self.root = None
        self.auxiliary_queue = []

    def level_build_tree(self, node):
        if self.root is None:
            self.root = node
            self.auxiliary_queue.append(node)
        else:
            if self.auxiliary_queue[0].left_child is None:
                self.auxiliary_queue[0].left_child = node
                self.auxiliary_queue.append(node)
            else:
                self.auxiliary_queue[0].right_child = node
                self.auxiliary_queue.append(node)
                self.auxiliary_queue.pop(0)

    def level_traverse(self, node):
        auxiliary_queue = []
        if node is None:
            return
        else:
            auxiliary_queue.append(node)
            while True:
                print(auxiliary_queue[0].val, end=' ')
                if auxiliary_queue[0].left_child is None:
                    break
                else:
                    auxiliary_queue.append(auxiliary_queue[0].left_child)
                    if auxiliary_queue[0].right_child is None:
                        break
                    else:
                        auxiliary_queue.append(auxiliary_queue[0].right_child)
                        auxiliary_queue.pop(0)


class Sort:
    def __init__(self, num=10):
        '''
        :param num:需要排序的list长度
        '''
        self.len = num
        self.sort_list = [3, 87, 2, 93, 78, 56, 61, 38, 12, 40]

    def partition(self, low, high):
        pivot = self.sort_list[high]  # 选择最后一个元素作为基准值
        k = low  # k 是小于基准值的元素的位置
        for i in range(low, high):
            if self.sort_list[i] < pivot:
                self.sort_list[i], self.sort_list[k] = self.sort_list[k], self.sort_list[i]
                k += 1
        # 将基准值放到正确的位置
        self.sort_list[k], self.sort_list[high] = self.sort_list[high], self.sort_list[k]
        return k  # 返回基准值的位置

    def quick_sort(self, low, high):
        if low < high:
            pivot = self.partition(low, high)  # 计算基准值的位置
            self.quick_sort(low, pivot - 1)  # 递归排序左半部分
            self.quick_sort(pivot + 1, high)  # 递归排序右半部分
        else:
            return


if __name__ == "__main__":
    # print('hi')
    # Tree = BiTree()
    # for i in range(1,11):
    #     Tree.level_build_tree(TreeNode(i))
    # Tree.level_traverse(Tree.root)

    list1 = Sort()
    print("Original list:", list1.sort_list)
    list1.quick_sort(0, list1.len - 1)
    print("Sorted list:", list1.sort_list)



